The application and use of dataforms, including common forms of bar codes, are extensive and growing. For present purposes, "dataform" is defined as including all arrangements whereby data is fixed in some form of machine readable copy. Typically dataforms comprise patterns of elements of differing reflectivity (black and white, for example) which can be printed on labels and other items. Basic aspects of encoding, reading or data extraction and decoding of dataforms are well known.
A MaxiCode is a form of two-dimensional dataform which includes a bull's eye target in the center of the dataform and a fixed number of hexagonal data cells surrounding the bull's eye pattern. A MaxiCode is shown in FIG. 1. A binary encoding protocol is utilized to represent encoded data by arrangements of black and white data cells. FIG. 2 is a diagrammatic map of the data cells of a MaxiCode. As shown, there are included 18 orientation cells marked "B" and "W" surrounding the bull's eye (which would be in the center). Of these orientation cells, those marked B are always black or of low reflectivity and those marked W are always white or of higher reflectivity. The known markings of these orientation cells enables determination of which of the four outer edges is the top edge of a MaxiCode. The remaining data cells can be black or white as determined by the data to be stored in a particular MaxiCode.
A dataform reader, whether using laser or image based technology, is typically programmed to implement a particular reading protocol designed for use with a specific form of dataform, such as a MaxiCode. Decoding normally includes two basic steps. The first is data extraction which includes processing image data to determine the black or white reflectivity characteristic of each dataform cell. The second step is decoding based on the binary black or white value of each data cell. For example, a MaxiCode label as illustrated includes 866 hexagonal data cells each having a binary 1 (black) or 0 (white) value. Data extraction includes processing image data representative of illumination reflected from a MaxiCode positioned in a target area in order to generate 866 bits of binary data. Decoding includes processing the binary data to recover the data file originally encoded in compressed or other form into the binary values of the data cells of the MaxiCode.
Background on MaxiCode Data Extraction
A typical prior MaxiCode data extraction method includes the following steps. First, locate the MaxiCode in the image area. Second, scale the MaxiCode image into a square bit mapped image area of 128.times.128 pixels. Third, find the three principal MaxiCode axes by use of Fourier transform techniques. Fourth, determine a grid location for each data cell by use of inverse Fourier transform techniques. Fifth, superimpose the grid locations onto the scaled image area. Sixth, use the grid locations to extract the binary value of each cell.
The method as described inherently involves a tradeoff between resolution level versus the level of data processing and processing time involved. Scaling to 128.times.128 pixels limits resolution and effects accuracy of results. Because of the high levels of processing required for Fourier transforms, doubling the resolution quadruples the processing time. Increasing the resolution to 512.times.512 pixels would increase processing time by a factor of at least 16. Increased processing time decreases operational effectiveness of a reader. Also, Fourier transform operations require use of a floating point processor, increasing cost and power consumption as compared to a fixed point processor. General background information relating to MaxiCodes is provided in U.S. Pat. No. 4,998,010 issued Mar. 5, 1991. For present purposes, a "MaxiCode type of dataform" is a dataform as illustrated in FIGS. 1 and 2 or as otherwise described in said patent, subject to inclusion of features or characteristics as described in particular implementations herein.
In view of the foregoing, objects of the present invention are to provide new and improved methods of extracting data from MaxiCode and other types of dataforms which are characterized by one or more of the following capabilities:
data extraction using spatial domain features; PA1 data extraction at relatively high resolution levels; PA1 data extraction without Fourier transform processing; PA1 bull's eye center location by intersection of diameters identified by unique T-sequence; PA1 dataform axis identification by use of data cell moment determinations; PA1 dataform axis identification by use of normalized cell traversal; and PA1 data cell sampling orientation by reference to normalized cell traversal. PA1 (a) providing pixel data for an image area, the pixel data representative of illumination reflected from the MaxiCode; PA1 (b) locating the center of the bull's eye pattern by sampling lines of pixel data to identify two intersecting diameters of the bull's eye pattern, each diameter identified by a pixel data T-sequence pattern uniquely characteristic of a bull's eye diameter; PA1 (c) determining, by moment analysis of a portion of the pixel data, the orientation of a least one MaxiCode axis normal to sides of hexagonal data cells, such orientation corresponding to the derived moment of a group of data cells in side-to-side straight line alignment; PA1 (d) determining the alignment of the top of the MaxiCode in said image area, based upon the location of a plurality of said orientation cells relative to the location of the bull's eye center, and extracting data from data cells of the MaxiCode by sampling image data along lines aligned with a MaxiCode axis; and PA1 (e) decoding the extracted data to recover information encoded into the Maxicode.